class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        
        self.n = len(candidates)
        self.target = target
        self.result = []
        self.path = []
        self.sums = 0
        self.backtracking(0,candidates)
        return self.result

    def backtracking(self,start_index:int,candidates):

        if self.sums==self.target:
            self.result.append(self.path[:])
            return
        if self.sums > self.target:
            return
        if start_index>=self.n:
            return
        for i in range(start_index,self.n):
            self.sums += candidates[i]
            self.path.append(candidates[i])

            self.backtracking(i,candidates)

            self.sums -= candidates[i]
            self.path.pop()
            

s = Solution()
s.combinationSum([2,3,6,7],7)
